Computing devices use data structures to efficiently store and access data. Different data structures may be better at handling large amounts of data, accessing data, or minimizing storage space. Some data structures are a collection of key-value pairs where the computing device uses the key to access one or more values that correspond to the key.
A multimap is a data structure that stores key-value pairs. The data type for each key and value can vary according to the type of multimap, but can include strings and integers. Each key can map to more than one value. For example, the key “chocolate” can map to both “cake” and “pudding” such that the multimap will return both values “cake” and “pudding” when given the key “chocolate.”
A trie is a data structure that stores key-value pairs. In a trie, the keys and the values can be strings or integers, and each key can only map to one value. Some tries, such as the ones discussed in this application, may limit the values to integers. A trie is tree structure such that a root node is linked to a number of nodes and each of those nodes can link to other nodes. Linked nodes contain keys. Nodes can also link to leaves. A leaf is a type of node that contains a value that corresponds to a key. Leaves do not link to additional nodes. Each node contains one character, and each leaf contains an integer. For example, to access the value for the key “chocolate,” a computing device traverses the nodes of the trie that contain the letters “c,” “h,” “o,” “c,” “o,” “l,” “a,” “t,” and “e.” The node “e” links to the leaf that contains the value for “386” which is the value for the key “chocolate.”